package leetcode.newVersion.array;

import java.util.ArrayList;
import java.util.Arrays;

public class lc56 {
    /*
    首先对区间进行排序保证重叠区间连续，接着通过判断两区间是否重叠，如果不重叠则加入结果集，如果重叠则更新结果集中最后一个区间的结束值。
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][];

        ArrayList<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b)->  a[0] - b[0]);//自定义升序排序

        // 先添加第一个区间
        res.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = res.get(res.size() - 1); // 获取结果集中最后一个区间
            int[] current = intervals[i]; // 当前遍历的区间

            if (last[1] >= current[0]) { // 有重叠
                // 合并区间：更新最后一个区间的结束值
                last[1] = Math.max(last[1], current[1]);
            } else { // 无重叠
                res.add(current);
            }
        }

        int[][] resArray = res.toArray(new int[res.size()][]);
        return resArray;
    }

    public static void main(String[] args) {
        lc56 obj = new lc56();
        int[][] arr1 = new int[][]{{4,7},{1,4}};
        System.out.println(Arrays.deepToString(obj.merge(arr1)));
        int[][] arr2 = new int[][]{{1,3},{2,6},{8,10},{15,18}};
        System.out.println(Arrays.deepToString(obj.merge(arr2)));
    }
}
